package list;


//链表的每个节点
class Node{
    //每个节点保存的值
    public String value;
    //下一个节点
    public Node next;
    public Node(String value){
        this.value = value;
        this.next = null;
    }
}
public class MyLinkedList {
    //头节点
    public Node head = null;

    //头插
    public void addFirst(String value){
        Node newNode = new Node(value);
        newNode.next = head;
        head = newNode;
    }
    //尾插
    public void addLast(String value){
        //特殊处理
        if (head == null){
            addFirst(value);
            return;
        }
        Node tail = head;
        for (tail = head; tail != null; tail = tail.next){
            if (tail.next == null){
                break;
            }
        }
        Node newNode = new Node(value);
        tail.next = newNode;
        newNode.next = null;
    }
    //指定位置插入
    public void add(int index ,String value){
        //合法性判断
        if (index < 0 || index > size()){
            throw new RuntimeException("下标异常");
        }
        //特殊情况处理
        if (index == 0){
            addFirst(value);
            return;
        }
        //找到要插入位置的前一个节点
        Node prve = head;
        for (int i = 0; i < index - 1; i++){
            prve = prve.next;
        }
        //此时 prev 就指向要插入元素的前一个位置
        Node newNode = new Node(value);
        newNode.next = prve.next;
        prve.next = newNode;
    }
    //按照下标来删除
    public String remove(int index){
        //判断合法性
        if (index < 0 || index >= size()){
            throw new RuntimeException("下标超出范围");
        }
        //特殊情况处理
        if (index == 0){
            String elem = head.value;
            head = head.next;
            return elem;
        }
        //找到要删除元素的前一个节点
        Node prve = head;
        for (int i = 0; i < index - 1; i++){
            prve = prve.next;
        }
        //此时 prev 就指向了要删除元素的前一个节点
        Node toRemove = prve.next;
        String value = toRemove.value;
        prve.next = toRemove.next;
        return value;
    }

    //按照值来删除
    public boolean remove(String value){
        //如果链表为空
        if (head == null){
            return false;
        }
        //特殊情况
        if (head.value.equals(value)){
            head = head.next;
            return true;
        }
        //先找到要删除的前一个节点
        //遍历链表,找到要删除的值
        Node prve = head;
        for (prve = head; prve != null; prve = prve.next){
            if (prve.next != null && prve.next.value.equals(value)){
                break;
            }
        }
        //两种情况
        //1.没找到
        if (prve == null){
            return false;
        }
        //2.找到了 ，进行删除操作
        Node toRemove = prve.next;
        prve.next = toRemove.next;
        return true;
    }

    //判断某个元素是否在链表中存在
    public boolean contains(String value){
         //遍历链表
        for (Node cur = head; cur != null; cur = cur.next){
            if (cur.value.equals(value)){
                return true;
            }
        }
        return false;
    }
    //找到某个元素的下标
    public int indexOf(String value){
        int index = 0;
        for (Node cur = head; cur != null; cur = cur.next){
            if (cur.value.equals(value)){
                return index;
            }
            index++;
        }
        return -1;
    }
    //清空链表
    public void clean(){
        head = null;
    }

    //求链表的长度
    public int size(){
        int size = 0;
        for (Node cur = head; cur != null; cur = cur.next){
            size++;
        }
        return size;
    }
    public String toString(){
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append("[");
        for (Node cur = head; cur != null; cur = cur.next){
            stringBuilder.append(cur.value);
            if (cur.next != null){
                stringBuilder.append(", ");
            }
        }
        stringBuilder.append("]");
        return stringBuilder.toString();
    }
}